﻿#include "stringtool.h"



// optimisations de dlDistance
int distance[50][50];
int s1[50];
int s2[50];


// fonctions pour SOUNDEX
//----------------------------------------------------
char StringTool::soundexInternalCode (const char& car)
{
    char ret = '\0';
    switch (car)
    {
        case 'B':
        case 'P':
            ret = '1';
        break;

        case 'C':
        case 'K':
        case 'Q':
            ret = '2';
        break;

        case 'D':
        case 'T':
            ret = '3';
        break;

        case 'L':
            ret = '4';
        break;

        case 'M':
        case 'N':
            ret = '5';
        break;

        case 'R':
            ret = '6';
        break;

        case 'G':
        case 'J':
            ret = '7';
        break;

        case 'X':
        case 'Z':
        case 'S':
            ret = '8';
        break;

        case 'F':
        case 'V':
            ret = '9';
        break;
    }

    return ret;
}
//----------------------------------------------------------------------------------
QString StringTool::removeFrom (const QString &word, const QString &letters)
{
    // retourne les lettres de word qui ne sont pas dans letters
    QString ret (word);

    QString::const_iterator iter;

    for (iter = letters.constBegin () ; iter != letters.constEnd () ; iter++)
    {
        ret.remove (*iter);
    }

    return ret;
}

//---------------------------------------------------
QString StringTool::soundexCode (const QString& word)
{
    //    Supprimer les éventuels 'espace' initiaux et finaux
    //    Mettre le mot en majuscule
    QString maj = word.toLatin1 ().trimmed ().toUpper ();

    //    Garder la première lettre
    //    Conserver la première lettre de la chaîne
    QChar firstLetter = maj.at (0);
    QString tmp1 = maj.mid (1);

    //    Supprimer toutes les occurrences des lettres : a, e, h, i, o, u, w, y
    //	  (à moins que ce ne soit la première lettre du nom)

    QString tmp2 (removeFrom (tmp1, soundexLettersToDelete ()));

    //    Attribuer une valeur numérique aux lettres restantes de la manière suivante :
    //        Version pour l'anglais :
    //            1 = B, F, P, V
    //            2 = C, G, J, K, Q, S, X, Z
    //            3 = D, T
    //            4 = L
    //            5 = M, N
    //            6 = R
    //        Version pour le français :
    //            1 = B, P
    //            2 = C, K, Q
    //            3 = D, T
    //            4 = L
    //            5 = M, N
    //            6 = R
    //            7 = G, J
    //            8 = X, Z, S
    //            9 = F, V

    QString tmp3;

    foreach (const QChar& car, tmp2)
    {
        tmp3 += soundexInternalCode (car.toLatin1 ());
    }


    // Si deux lettres (ou plus) avec le même nombre sont adjacentes dans le nom d'origine,
    // ou s'il n'y a qu'un h ou un w entre elles, alors on ne retient que la première de ces lettres.

    QString tmp4 (uniqueLetters (tmp3));

    // Renvoyer les quatre premiers octets complétés par des zéros.

    QString tmp5 (QString ("%1%20000")
                  .arg (firstLetter)
                  .arg (tmp4.left (3)));

    return tmp5.left (4);

}
//----------------------------------------------------------------------------------------------------
int StringTool::dlDistance (const QString &str1, const QString &str2, bool damerau, const int& maxDiff)
{
    // cf. http://fr.wikipedia.org/wiki/Distance_de_Damerau-Levenshtein

    const int lenStr1 = str1.size ();
    const int lenStr2 = str2.size ();

    if (abs (lenStr1 - lenStr2) > maxDiff) return -1;

    const QChar* chars1 = str1.constData ();
    const QChar* chars2 = str2.constData ();

    int (*d)[50] = distance;


    // **************** calcul de la distance ****************
    // ligne et colonne 0
    for (int i = 0 ; i <= lenStr1 ; i++)
        d[i][0] = i;

    for (int j = 0 ; j <= lenStr2 ; j++)
        d[0][j] = j;

    // lignes suivantes

    if (damerau) {
        // si damerau == true (dans mcroises.conf au démarrage de l'appli) on teste les transpositions
        for (int i = 1; i <= lenStr1 ; i++) {
            int maxOfLine = 0xff;

            for (int j = 1; j <= lenStr2 ; j++) {
                const int cost = (str1.at (i-1) == str2.at (j-1)) ? 0 : 1;

                int best = min (1 + min (d[i-1][j],     		// suppression
                                         d[i][j-1]),			// insertion
                                d[i-1][j-1] + cost);			// substitution

                if (i > 1 && j > 1)	{ // damerau = tester les transpositions (i >= 2, j >= 2)
                    if (str1.at (i-1) == str2.at (j-2) && str1.at (i-2) == str2.at (j-1)) {
                        best = min (best,
                                    d[i-2][j-2] + cost);	// transposition
                    }
                }

                d[i][j] = best;
                if (maxOfLine > best) maxOfLine = best;
            }

            if (maxOfLine > maxDiff) return -1;
        }
    }
    else
    {
        for (int i = 1 ; i <= lenStr1 ; i++)
        {
            int i_1 = i-1;
            const QChar& chars1i = chars1[i_1];
            int maxOfLine = 1024;
            {
                for (int j = 1 ; j <= lenStr2 ; j++)
                {
                    int j_1 = j-1;
                    const QChar& chars2j = chars2[j_1];

                    const int cost = (chars1i == chars2j) ? 0 : 1;
                    int best = min (d[i_1][j],				// suppression
                                     d[i][j_1]) + 1;		// insertion

                    best = min (best,
                                 d[i_1][j_1] + cost);		// substitution

                    d[i][j] = best;
                    maxOfLine = min (maxOfLine, best);
                }

                if (maxOfLine > maxDiff) return -1;
            }
        }
    }

    int result = d[lenStr1][lenStr2];

    return (result > maxDiff ? -1 : result);
}
